#include <stdio.h>
#include <stdlib.h>

typedef enum { false, true } bool;
typedef int ElemSet; /* 默认元素为整型 */
typedef enum { Red, Black } Color;
typedef struct RecordNode *Records;
struct RecordNode {
    ElemSet key; /* 关键字 */
    /* 其他属性由用户自定义 */
};

typedef Records TElemSet;
typedef struct RBTreeNode *Position; /* 树结点指针是元素的位置 */
typedef struct RBTreeNode *RBTree;
struct RBTreeNode {
    TElemSet data; /* 数据元素 */
    RBTree left; /* 左孩子指针 */
    RBTree right; /* 右孩子指针 */
    Color color; /* 颜色 */
    RBTree parent; /* 父指针 */
};
#define NIL NULL

void Visit(RBTree tree) {
    if (tree->color == Red) {
        printf("%d\n", -tree->data->key);
    } else {
        printf("%d\n", tree->data->key);
    }
}

void PreOrder(RBTree tree) {
    if (tree != NIL) {
        Visit(tree);
        PreOrder(tree->left);
        PreOrder(tree->right);
    }
}

/* 算法12-7：红黑树中的右旋 RRotate(rbtree, x) */
RBTree RRotate(RBTree rbtree, Position x) {
    Position y, p;

    y = x->left;
    p = x->parent;
    x->left = y->right; /* 调整x */
    if (x->left != NIL) {
        x->left->parent = x;
    }
    x->parent = y;
    y->right = x; /* 调整y */
    if (x == rbtree) {
        rbtree = y;
        y->parent = NIL;
    } else {
        y->parent = p;
        if (p->left == x) {
            p->left = y;
        } else {
            p->right = y;
        }
    }
    return rbtree;
}
/* 算法12-7 结束 */

RBTree LRotate(RBTree rbtree, Position x) {
    Position y, p;

    y = x->right;
    p = x->parent;
    x->right = y->left; /* 调整x */
    if (x->right != NIL) {
        x->right->parent = x;
    }
    x->parent = y;
    y->left = x; /* 调整y */
    if (x == rbtree) {
        rbtree = y;
        y->parent = NIL;
    } else {
        y->parent = p;
        if (p->left == x) {
            p->left = y;
        } else {
            p->right = y;
        }
    }
    return rbtree;
}

/* 算法12-8：红黑树中插入结点后的调整 InsertAdjust(rbtree, x) */
RBTree InsertAdjust(RBTree rbtree, Position x) {
    Position p, gp, y;

    p = x->parent; /* p是x的父结点 */
    while (p != NIL
    && p->color == Red) { /* x和父结点都是红色，需要调整 */
        gp = p->parent; /* gp是x的祖先结点 */
        if (p == gp->left) { /* p是gp的左孩子 */
            y = gp->right; /* y是p的兄弟结点*/
            if (y != NIL
            && y->color == Red) { /* 第一种情况：p及其兄弟结点都是红色 */
                p->color = Black;
                y->color = Black;
                gp->color = Red;
                x = gp;
                p = x->parent;
            } else { /* 第二种情况：p的兄弟是黑结点 */
                if (x == p->right) { /* LR形态 */
                    rbtree = LRotate(rbtree, p);
                    p = x;
                    x = p->left;
                } /* 至此保证x是p的左孩子，即LL形态 */
                p->color = Black;
                gp->color = Red;
                rbtree = RRotate(rbtree, gp); /* 此时p是黑色，退出循环 */
            }
        } else { /* p是gp的右孩子，与以上代码完全对称 */
            y = gp->left; /* y是p的兄弟结点 */
            if (y != NIL
            && y->color == Red) { /* 第一种情况：p及其兄弟结点都是红色 */
                p->color = Black;
                y->color = Black;
                gp->color = Red;
                x = gp;
                p = x->parent;
            } else { /* 第二种情况：p的兄弟是黑结点 */
                if (x == p->left) { /* RL形态 */
                    rbtree = RRotate(rbtree, p);
                    p = x;
                    x = p->right;
                } /* 至此保证x是p的右孩子，即RR形态 */
                p->color = Black;
                gp->color = Red;
                rbtree = LRotate(rbtree, gp); /* 此时p是黑色，退出循环 */
            }
        }
    }
    rbtree->color = Black; /* 确保树根为黑色 */
    return rbtree;
}
/* 算法12-8 结束 */

bool IsBlack(Position x) {
    if (x == NIL || (x != NIL && x->color == Black)) {
        return true;
    } else
        return false;
}

bool IsRed(Position x) {
    return (IsBlack(x) == false);
}

/* 算法12-9：删除黑结点及颜色调整 DeleteAdjust(rbtree, x) */
RBTree DeleteAdjust(RBTree rbtree, Position x) {
    Position p, w;

    p = x->parent; /* p是x的父结点 */
    while (x != rbtree
    && x->color == Black) { /* x是黑色的非根结点，需要调整 */
        if (x == p->left) { /* x是左孩子 */
            w = p->right; /* w是x的兄弟结点 */
            if (w->color == Red) { /* 情况(1)：兄弟是红色 */
                w->color = Black;
                p->color = Red;
                rbtree = LRotate(rbtree, p);
                w = p->right;
            } /* 此时保证x和兄弟都是黑色，即情况(2)~(4) */
            if (IsBlack(w->left) && IsBlack(w->right)) { /* 情况(2)：w双子黑色 */
                w->color = Red;
                x = p;
                p = x->parent; /* 继续循环 */
            } else {
                if (IsRed(w->left) && IsBlack(w->right)) { /* 情况(3)：w左红右黑 */
                    w->color = Red;
                    w->left->color = Black;
                    rbtree = RRotate(rbtree, w);
                    w = p->right;
                } /* 此时保证x的兄弟w右孩子是红色，即情况(4) */
                w->color = p->color;
                p->color = Black;
                w->right->color = Black;
                rbtree = LRotate(rbtree, p);
                x = rbtree; /* 此设置只为跳出循环 */
            }
        } else { /* x是右孩子，与以上代码完全对称 */
            w = p->left; /* w是x的兄弟结点 */
            if (w->color == Red) { /* 情况(1)：兄弟是红色 */
                w->color = Black;
                p->color = Red;
                rbtree = RRotate(rbtree, p);
                w = p->left;
            } /* 此时保证x和兄弟都是黑色，即情况(2)~(4) */
            if (IsBlack(w->left) && IsBlack(w->right)) { /* 情况(2)：w双子黑色 */
                w->color = Red;
                x = p;
                p = x->parent; /* 继续循环 */
            } else {
                if (IsRed(w->right) && IsBlack(w->left)) { /* 情况(3)：w右红左黑 */
                    w->color = Red;
                    w->right->color = Black;
                    rbtree = LRotate(rbtree, w);
                    w = p->left;
                } /* 此时保证x的兄弟w左孩子是红色，即情况(4) */
                w->color = p->color;
                p->color = Black;
                w->left->color = Black;
                rbtree = RRotate(rbtree, p);
                x = rbtree; /* 此设置只为跳出循环 */
            }
        }
    }
    x->color = Black; /* 若x是红色则染黑，或保证根结点是黑色 */
    return rbtree;
}
/* 算法12-9 结束 */

RBTree InsertRBT(RBTree rbtree, TElemSet record) {
    Position x, parent;
    if (rbtree == NIL) { /* 如果是空树，创建根结点 */
        rbtree = (RBTree)malloc(sizeof(struct RBTreeNode));
        rbtree->data = record;
        rbtree->color = Black; /* 根结点是黑色 */
        rbtree->left = rbtree->right
                       = rbtree->parent
                         = NIL;
    } else {
        parent = NIL;
        x = rbtree;
        while (x != NIL) { /* 寻找适合插入record的位置 */
            parent = x;
            if (record->key < x->data->key) {
                x = x->left;
            } else if (record->key > x->data->key) {
                x = x->right;
            } else { /* 找到record.key，更新record的其它属性 */
                break;
            }
        }
        if (x == NIL) { /* record应该插入为parent的子结点 */
            x = (RBTree)malloc(sizeof(struct RBTreeNode));
            x->data = record;
            x->parent = parent;
            x->left = x->right = NIL;
            x->color = Red;
            if (record->key < parent->data->key) {
                parent->left = x;
            } else {
                parent->right = x;
            }
            rbtree = InsertAdjust(rbtree, x);
        }
    }
    return rbtree;
}

RBTree DeleteRBT(RBTree rbtree, ElemSet key) {
    Position deleted, x;

    if (rbtree == NIL) { /* 若是空树 */
        printf("错误：%d不在树中。\n", key);
    } else { /* 若不是空树 */
        deleted = rbtree;
        while (deleted != NIL) { /* 寻找key所在的位置 */
            if (key < deleted->data->key) {
                deleted = deleted->left;
            } else if (key > deleted->data->key) {
                deleted = deleted->right;
            } else { /* 找到key所在的位置deleted */
                break;
            }
        }
        if (deleted == NIL) {
            printf("错误：%d不在树中。\n", key);
        } else {
            if (deleted->left != NIL && deleted->right != NIL) { /* 左右子树都有 */
                x = deleted->left; /* x用于寻找中序遍历中deleted的直接前驱 */
                while (x->right != NIL) {
                    x = x->right;
                }
                deleted->data = x->data; /* 用前驱的数据替换deleted的数据 */
                deleted = x; /* 此时deleted最多只有一棵子树 */
            }
            if (deleted->color == Black) {
                x = deleted;
                rbtree = DeleteAdjust(rbtree,
                                      x); /* 在根到deleted的路径上多加一个黑结点 */
            }
            if (deleted->left == NIL) {
                x = deleted->right;
            } else if (deleted->right == NIL) {
                x = deleted->left;
            } /* 此时x指向deleted唯一子树，或NIL */
            if (deleted->parent == NIL) { /* 删除根结点 */
                if (x != NIL) {
                    x->color = Black; /* 若x是红色则染黑，或保证根结点是黑色 */
                }
                rbtree = x;
            } else if (deleted == deleted->parent->left) {
                deleted->parent->left = x;
            } else {
                deleted->parent->right = x;
            }
            if (x != NIL) {
                x->parent = deleted->parent;
            }
            free(deleted); /* 释放删除的结点空间 */
        }
    }
    return rbtree;
}

int main(void) {
    RBTree rbtree;
    Records record;
    ElemSet key;
    int n, m, i;

    rbtree = NIL;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        record = (Records)malloc(sizeof(struct RecordNode));
        scanf("%d", &record->key);
        rbtree = InsertRBT(rbtree, record);
    }
    PreOrder(rbtree);
    printf("\n");
    scanf("%d", &m);
    for (i = 0; i < m; i++) {
        scanf("%d", &key);
        rbtree = DeleteRBT(rbtree, key);
        PreOrder(rbtree);
        printf("\n");
    }

    return 0;
}